package com.bestdreamer.linkedlist;

/**
 * 给定一个带头结点的单链表，请将其逆序。
 * 即如果单链表原来为 head→1→2→3→4→5→6→7，则逆序为 head→7→6→5→4→3→2→1
 */
public class Test01 {

    /**
     * 方法一：就地逆序
     */
    public static void Reverse(LNode head) {
        // 判断链表是否为空
        if (head == null || head.next == null)
            return;
        LNode pre = null;   // 前驱结点
        LNode cur = null;   // 当前结点
        LNode next = null;  // 后继结点
        // 把链表首结点变为尾结点
        cur = head.next;
        next = cur.next;
        cur.next = null;
        pre = cur;
        cur = next;
        // 使当前遍历到的结点 cur 指向其前驱结点
        while (cur.next != null) {
            next = cur.next;
            cur.next = pre;
            pre = cur;
            cur = cur.next;
            cur = next;
        }
        // 结点最后一个结点指向倒数第二个结点
        cur.next = pre;
        // 链表的头结点指向原来链表的尾结点
        head.next = cur;
    }

    public static void main(String[] args) {
        // 链表头结点
        LNode head = new LNode();
        head.next = null;
        LNode tmp = null;
        LNode cur = head;
        // 构造单链表
        for(int i=1; i< 8; i++ ){
            tmp = new LNode();
            tmp.data = i;
            tmp.next = null;
            cur.next = tmp;
            cur = tmp;
        }
        System.out.print("逆序前：");
        for(cur = head.next; cur != null; cur = cur.next)
            System.out.print(cur.data + " ");
        System.out.print("\n 逆序后：");
        Reverse(head);
        for(cur = head.next; cur != null; cur = cur.next)
            System.out.print(cur.data + " ");

    }

}
